#include <iostream>
#include <vector>

using namespace std;
class Solution
{
public:
    int sumOddLengthSubarrays(vector<int> &arr)
    {
        int sum = 0;
        int n = arr.size();
        for (int start = 0; start < n; start++)
        {
            for (int length = 1; start + length <= n; length += 2)
            {
                int end = start + length - 1;
                for (int i = start; i <= end; i++)
                {
                    sum += arr[i];
                }
            }
        }
        return sum;
    }

    int sumOddLengthSubarrays_2(vector<int> &arr)
    {
        int n = arr.size();
        vector<int> prefixSums(n + 1);
        for (int i = 0; i < n; i++)
        {
            prefixSums[i + 1] = prefixSums[i] + arr[i];
        }
        int sum = 0;
        for (int start = 0; start < n; start++)
        {
            // 1 ,n-length  +=2
            for (int length = 1; start + length <= n; length += 2)
            {
                int end = start + length - 1;
                sum += prefixSums[end + 1] - prefixSums[start];
            }
        }
        return sum;
    }

    int sumOddLengthSubarrays_3(vector<int> &arr)
    {
        int sum = 0;
        int n = arr.size();
        for (int i = 0; i < n; i++)
        {
            int leftCount = i, rightCount = n - i - 1;
            int leftOdd = (leftCount + 1) / 2;
            int rightOdd = (rightCount + 1) / 2;
            int leftEven = leftCount / 2 + 1;
            int rightEven = rightCount / 2 + 1;
            sum += arr[i] * (leftOdd * rightOdd + leftEven * rightEven);
        }
        return sum;
    }
};

int main()
{
    Solution s;
    vector<int> arr = {1, 4, 2, 5, 3};
    cout << s.sumOddLengthSubarrays(arr) << endl;
    system("pause");
    return 0;
}
